rg = require "random_graphs" 
ts = require "topological_sort"

function run_timed (reps, fn, ...) 
   local t0 = os.clock() 
   for i = 1,reps do 
      fn(...)
   end
   local t1 = os.clock() 
   return (t1-t0)
end 

function graph_count_edges(g) 
   local ct = 0 
   for n,es in ipairs(g) do 
      ct = ct + #es
   end 
   return ct 
end 


function tabulate_edges(nodes, density) 
   local results = {} 
   for i = 1,1000 do 
      local g = rg.build_random_dag(nodes, density) 
      local ct = graph_count_edges(g)

      if results[ct] then results[ct] = results[ct] + 1 
      else results[ct] = 1 
      end 
   end 
   return results 
end 

function tabulate_ts_times(start_nodes, reps, step, density)
   local results = {} 
   for nodes = start_nodes, start_nodes+(step*reps), step do 
      local cumulative = 0 
      for i = 1,20 do 
	 local g = rg.build_random_dag(nodes, density) 
	 local t0 = os.clock() 
	 ts.topological_sort(g) 
	 local t1 = os.clock() 
	 cumulative = cumulative+(t1-t0)
      end 
      results[nodes] = cumulative/20 
      --print(".") 
   end 
   return results 
end 

function tabulate_ts_comparisons(start_nodes, reps, step, density)
   local results = {} 
   for nodes = start_nodes, start_nodes+(step*reps), step do 
		local cumulative = 0 
		
		for i = 1,20 do 
			
			local g = rg.build_random_dag(nodes, density) 
			ts.comparisonCount = 0
			
			ts.topological_sort(g) 
			
			cumulative = cumulative+ts.comparisonCount
		end 
      
		results[nodes] = cumulative/20 
		--print(".") 
   end 
   return results 
end 

--[[
for nodes=100, 1000, 100 do
	local outputLine = nodes .. "\t\t"
	
	for density=0.1, 1.0, 0.1 do
		outputLine = outputLine .. "\t" .. graph_count_edges( rg.build_random_dag(nodes, density) )
	end
	
	print( outputLine )
end 
]]--

--[[
for i=0.1, 1.0, 0.1 do
	local results = tabulate_ts_times(100, 10, 10, i)
	local str = i .. "\t"
	
	for i=100, 100+100, 10 do
		str = str .. results[i] .. "\t"
	end
	print( str )
end
]]--
for i=0.1, 1.0, 0.1 do
	local results = tabulate_ts_comparisons(100, 10, 10, i)
	local str = i .. "\t"
	
	for i=100, 100+100, 10 do
		str = str .. results[i] .. "\t"
	end
	print( str )
end


